这道题边的数量最高是10000多，而点只有500，这提醒我们，我们不能直接对边求期望，而是点。
设表示点的期望走过次数，表示点的度数。
那么，
CF85E Guard Towers
注意题目中的这句话 : 使得同组内的两座塔的曼哈顿距离的最大值最小 , 很容易想到二分。
考虑二分一个长度，显然，当两个点的曼哈顿距离大于时，它们不能属于同一个集合。
我们将这样的点对连一条边，原问题等价与判断新图是否为一个二分图。
CF559C Gerald and Giant Chess
如果没有不能走到的点，这道题就非常简单了。我们只需向下走步，向右走步，就可到达右下角。在这步中，我们选向下走，那么答案为。
但是，棋盘中有些点是不能走的，我们考虑用容斥原理去除多余方案，即
CF167E Wizards and Bets
首先，我们将所有源点与汇点筛出来，然后从每一个源点dfs求出它到各汇点的路径数，题目中保证源点与汇点数量相同，我们记为。
那么，我们可以得到一个的矩阵。
先考虑路径不相交的情况（似乎大家思路都是这样），题目求的是一个排列的逆序对数，记为。那么，题目等价于求：
P1769 淘汰赛制
与题目定义有些不同，表示人数，表示淘汰赛轮数。题目显然输入的是,根据它算出。为了方便2进制计算，编号从~。最后答案加1即可。同时，比赛胜败概率为了方便先除以100，用计算。
现在考虑如何计算答案，设为对的胜率，为第轮胜出的概率。那么有：
CF147B Smile House
貌似 @DDF_Van 大佬的标程过不了 ， 有些题解用的二分会多一个，那就补一发倍增题解吧。
Solution 1
设表示走了不多于条边，的最大边权(走不通为极小值)
P2146 [NOI2015]软件包管理器
这其实是一道树链剖分的板题，难在读题...
借一下洛谷的图：（将边看成无向的）
P3704 [SDOI2017]数字表格
前置知识：莫比乌斯反演，数论分块
题意
P2922 秘密消息
这道题还是树的板题，先将个信息插入字典树中，对于查询的密码，在字典树中查询即可。
插入很好办，我们现在来讨论查询操作。我们记为任意一个信息，是待匹配的密码。表示有多少个字符串经过点，表示有多少个字符串以点结尾。
那么会出现三种情况：